package com.muchfish.algorithm.array;

/**
 * <a href="https://leetcode.cn/problems/container-with-most-water/description/">题目：11. 盛最多水的容器</a>
 * <br>
 * <img src="../../../../../image/PixPin_2024-09-11_20-45-19.jpg">
 * <img src="../../../../../image/PixPin_2024-09-11_22-42-53.jpg">
 */
public class Array1 {

    public static void main(String[] args) {
        int[] height = {8,7,6,5,4,3,2,12,9};
        System.out.println(maxArea(height));
    }

    public static int maxArea(int[] height) {
        //容量=两线横坐标之差（长）*两线最小纵坐标（高）
        //双指针法
        //双指针分别指向数组的首尾，每次比较两个指针所指的两条线的容量，将容量最大的赋给max
        //如果左边的线比较短，那么左指针向右移动，反之右指针向左移动
        // 原因：1.最长的长度只有一个，就是最左边和最右边组成的长度
        //      2.次长的长度有两个，最左边+1与最右边组成或最左边与最右边-1组成
        //      3.因此，次长中最左和最有都有可能参与计算，那么保留最左与最右中较长的一条线，就是次长两种情景中最优秀的解（移动哪个，是在两个次长的情况下的比较）（本条可忽略）
        //      4.同时，最长中最短的线，参与次长计算，因为长度减少，即使是高度不变，容量肯定也小于最长时容量。以此类推，最长中的短线参与次次长，次次次...长的计算，都将小于最长时的容量
        //      5.得出，最长中的短线，无需参与后续的所有计算。
        //      6.以此类推，每次比较中，较短的线，无需参与后续的所有计算，每次只保留较高的线即可
        //      7.就可以得到结论：如果左边的线比较短，那么左指针向右移动，反之右指针向左移动
        //遍历完就得到结果了，临界条件为左指针>=右指针
        int max = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            max = Math.max(max, area);
            if (height[left] < height[right]) {
                left++;
            }else {
                right --;
            }

        }

        return max;
    }

    /**
     * 暴力法
     * @param height
     * @return
     */
    public static int maxArea1(int[] height) {
        //容量=两线横坐标之差*两线最小纵坐标
        //暴力法
        //双层for循环，从第一条线开始，每一条线都与其他所有的线进行容量计算
        //使用临时变量存放最大容量
        //遍历完就得到结果了
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i+1; j < height.length; j++) {
                int temp = (j-i)*Math.min(height[i],height[j]);
                if (temp>max){
                    max = temp;
                }
            }
        }
        return max;
    }
}
